|
Title:
|
ATTRACTION A GLOBAL AFFINITY MEASURE FOR DATABASE VERTICAL PARTITIONING |
|
Author(s):
|
Jun Du , Ken Barker , Reda Alhajj |
|
ISBN:
|
972-98947-1-X |
|
Editors:
|
Pedro Isaías and Nitya Karmakar |
|
Year:
|
2003 |
|
Edition:
|
1 |
|
Keywords:
|
Data design, attraction function, attribute affinity matrix, vertical partitioning. |
|
Type:
|
Full Paper |
|
First Page:
|
538 |
|
Last Page:
|
548 |
|
Language:
|
English |
|
Cover:
|
|
|
Full Contents:
|
click to dowload 
|
|
Paper Abstract:
|
Vertical partitioning clusters attributes of a relation to generate fragments suitable for subsequent allocation over a distributed platform. Partitioning is also important for centralized and web databases because data items that are mostly accessed together should reside in the same fragment. The target is to minimize the execution time of user applications. Most previous algorithms for intuitive database partitioning design use the Attribute Affinity Matrix (AAM) directly. This paper proposes an attraction measure to enable global evaluation of attribute togetherness in a given relation. An attribute attraction matrix (AAM*) can also evolve from the AAM by selecting an appropriate attraction function. We further propose the connection-based partitioning approach to take advantage of the global comparability of the AAM*. Two such algorithms are presented in this paper. The Preliminary Connection-Based Partitioning Algorithm (PCBPA) finds the fragments with a complexity of O(m), where m is the number of edges found in the corresponding undirected connection graph of the AAM*. The
Connection-Based Partitioning Algorithm (CBPA) is capable of eliminating trivial fragments; it has a complexity measure of O(n2), where n is the number of attributes. Finally, we argue that the partitioning obtained based on the attraction measure is at least as good as the result from the algorithms that use the conventional affinity measure. |
|
|
|
|
|
|
